class Solution {
public:
/*
    如果设dp[i]为以i位置结尾的等差序列的个数，那么当要求dp[i]时，无法根据前面的dp[j]来求得，因为两个数并不能确定一个等差数列
    因此，根据两个数可以确定一个等差数列，可以设dp[j][i]为以j、i位置结尾的元素，等差序列的个数

    要求dp[j][i]，可以根据等差数列的性质，j位置前元素的大小应该为：nums[k] = 2 * nums[j] - nums[i]
    即dp[j][i] = dp[k][j] + 1(多了一个元素，等差数列的个数自然要多一个)
    又由于值为nums[k]的元素不止一个，因此要进行累加

    dp之前，可以先将nums中元素的大小和它的位置数组进行映射，方便后续计算
*/
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return 0;
        
        //建立数组元素和下标的映射关系
        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < nums.size(); i++)
            hash[nums[i]].push_back(i);

        //创建dp表
        int ret = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 2; i < n; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                long long prev_num = 2 * (long long)nums[j] - nums[i];
                if (hash.count(prev_num))
                {
                    for (auto& k : hash[prev_num])
                    {
                        //nums[k]必须在nums[j]之前
                        if (k >= j)
                            break;
                        dp[j][i] += dp[k][j] + 1;
                    }
                }

                ret += dp[j][i];
            }   
        }
        return ret;
    }
};